package com.unionpay.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ***********************************
 * 类描述： 默克尔树
 * 创建者： 瞿峰
 * 创建时间： 2016-5-12 下午02:36:35
 *************************************
 */
public class MerkleTree {

	public static final byte LEAF_SIG_TYPE = 0x0;
	public static final byte INTERNAL_SIG_TYPE = 0x01;

	private Node root;
	private int depth;
	private int nnodes;

	/**
	 * Use this constructor to create a MerkleTree from a list of leaf signatures.
	 * The Merkle tree is built from the bottom up.
	 * @param leafSignatures
	 */
	public MerkleTree(List<String> leafSignatures) {
		constructTree(leafSignatures);
	}

	/**
	 * Use this constructor when you have already constructed the tree of Nodes 
	 * (from deserialization).
	 * @param treeRoot
	 * @param numNodes
	 * @param height
	 * @param leafSignatures
	 */
	public MerkleTree(Node treeRoot, int numNodes, int height, List<String> leafSignatures) {
		root = treeRoot;
		nnodes = numNodes;
		depth = height;
	}

	/**
	 * Create a tree from the bottom up starting from the leaf signatures.
	 * @param signatures
	 */
	void constructTree(List<String> signatures) {
		if (signatures.size() <= 1) {
			throw new IllegalArgumentException("Must be at least two signatures to construct a Merkle tree");
		}

		nnodes = signatures.size();
		List<Node> parents = bottomLevel(signatures);
		nnodes += parents.size();
		depth = 1;

		while (parents.size() > 1) {
			parents = internalLevel(parents);
			depth++;
			nnodes += parents.size();
		}

		root = parents.get(0);
	}

	public int getNumNodes() {
		return nnodes;
	}

	public Node getRoot() {
		return root;
	}

	public int getHeight() {
		return depth;
	}

	/**
	 * Constructs an internal level of the tree
	 */
	List<Node> internalLevel(List<Node> children) {
		List<Node> parents = new ArrayList<Node>(children.size() / 2);

		for (int i = 0; i < children.size() - 1; i += 2) {
			Node child1 = children.get(i);
			Node child2 = children.get(i + 1);

			Node parent = constructInternalNode(child1, child2);
			parents.add(parent);
		}

		if (children.size() % 2 != 0) {
			Node child = children.get(children.size() - 1);
			Node parent = constructInternalNode(child, null);
			parents.add(parent);
		}

		return parents;
	}

	/**
	 * Constructs the bottom part of the tree - the leaf nodes and their
	 * immediate parents.  Returns a list of the parent nodes.
	 */
	List<Node> bottomLevel(List<String> signatures) {
		List<Node> parents = new ArrayList<Node>(signatures.size() / 2);

		for (int i = 0; i < signatures.size() - 1; i += 2) {
			Node leaf1 = constructLeafNode(signatures.get(i));
			Node leaf2 = constructLeafNode(signatures.get(i + 1));

			Node parent = constructInternalNode(leaf1, leaf2);
			parents.add(parent);
		}

		// if odd number of leafs, handle last entry
		if (signatures.size() % 2 != 0) {
			Node leaf = constructLeafNode(signatures.get(signatures.size() - 1));
			Node parent = constructInternalNode(leaf, null);
			parents.add(parent);
		}

		return parents;
	}

	private Node constructInternalNode(Node child1, Node child2) {
		Node parent = new Node();
		parent.type = INTERNAL_SIG_TYPE;

		if (child2 == null) {
			parent.sig = child1.sig;
		} else {
			parent.sig = internalHash(child1.sig, child2.sig);
		}

		parent.left = child1;
		parent.right = child2;
		return parent;
	}

	private static Node constructLeafNode(String signature) {
		Node leaf = new Node();
		leaf.type = LEAF_SIG_TYPE;
		leaf.sig = signature;
		return leaf;
	}

	String internalHash(String leftChildSig, String rightChildSig) {
		StringBuffer buffer = new StringBuffer();
		buffer.append(leftChildSig);
		buffer.append(rightChildSig);
		String result = SHA1.encode(buffer.toString());
		return result;
	}

	public static class Node {
		public byte type; // INTERNAL_SIG_TYPE or LEAF_SIG_TYPE
		public String sig; // signature of the node
		public Node left;
		public Node right;
	}
	public static void main(String[] args) {
		 List<String> signatures = Arrays.asList(
			        "00BD3A3A31dd93FdddA5AC3E32A841BBAAAAAAAA00A63A3A315293F612A5AC3E32A841BBAAAAAAAA00A63A3A315293F612A5AC3E32A841BBAAAAAAAA00000000881139f4f66189ccce33d66275b6e4f49fc2742a20160517154247", 
			        "00BD3A3A31dd93FdddA5AC3E32A841BBAAAAAAAA00A63A3A315293F612A5AC3E32A841BBAAAAAAAA00A63A3A315293F612A5AC3E32A841BBAAAAAAAA00000000881139f4f66189ccce33d66275b6e4f49fc2742a20160517154248",
			        "00BD3A3A31dd93FdddA5AC3E32A841BBAAAAAAAA00A63A3A315293F612A5AC3E32A841BBAAAAAAAA00A63A3A315293F612A5AC3E32A841BBAAAAAAAA00000000881139f4f66189ccce33d66275b6e4f49fc2742a20160517154248");
		 MerkleTree merkleTree=new MerkleTree(signatures);
		 System.out.println(merkleTree.root.sig);
	}
}
